package com.nowcoder.面试必刷101;

import java.util.Arrays;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;

/**
 * @Description: 删除最早最少调用
 * @author： yeswater
 * @create： 2024/6/14
 */

public class BM101 {
	
	public static void main(String[] args) {
		
	}
	
	class Node {
		int freq;
		int key;
		int val;
		
		public Node(int freq, int key, int val) {
			this.freq = freq;
			this.key = key;
			this.val = val;
		}
	}
	
	private Map<Integer, LinkedList<Node>> freq_map = new HashMap<>();
	private Map<Integer, Node> map = new HashMap<>();
	private int size = 0; // 记录缓存剩余容量
	private int min_freq = 0; // 记录当前最小频次
	
	
	public int[] LFU(int[][] operators, int k) {
		this.size = k;
		// opt=1 : set 
		// opt=2 : get
		int len = (int) Arrays.stream(operators).filter(x -> x[0] == 2).count();
		int[] res = new int[len];
		for (int i = 0, j = 0; i < operators.length; i++) {
			if (operators[i][0] == 1) {
				set(operators[i][1], operators[i][2]);
			} else {
				res[j++] = get(operators[i][1]);
			}
		}
		return res;
	}
	
	private void update(Node node, int key, int value) {
		int freq = node.freq;
		freq_map.get(freq).remove(node);
		if (freq_map.get(freq).isEmpty()) {
			freq_map.remove(freq);
			if (min_freq == freq)
				min_freq++;
		}
		if (!freq_map.containsKey(freq + 1))
			freq_map.put(freq + 1, new LinkedList<Node>());
		freq_map.get(freq + 1).addFirst(new Node(freq + 1, key, value));
		map.put(key, freq_map.get(freq+1).getFirst());
	}
	
	public int get(int key) {
		int res = -1;
		if (map.containsKey(key)) {
			Node node = map.get(key);
			res = node.val;
			update(node, key, res);
		}
		return res;
	}
	
	public void set(int key, int value) {
		if (map.containsKey(key))
			update(map.get(key), key, value);
		else {
			if (size == 0) {
				int oldkey = freq_map.get(min_freq).getLast().key;;
				freq_map.get(min_freq).removeLast();
				if (freq_map.get(min_freq).isEmpty())
					freq_map.remove(min_freq);
				map.remove(oldkey);
			} else {
				size--;
			}
			min_freq = 1;
			//在频率为1的双向链表表头插入该键
			if(!freq_map.containsKey(1))
				freq_map.put(1, new LinkedList<Node>());
			freq_map.get(1).addFirst(new Node(1, key, value));
			//哈希表key值指向链表中该位置
			map.put(key, freq_map.get(1).getFirst());
		}
	}
}
